package linkedList.双指针;

import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N环形链表II142.java
 * @Description  https://leetcode-cn.com/problems/linked-list-cycle-ii/
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
 * @createTime 2021年03月11日 19:39:00
 */
public class N环形链表II142 {

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slowPoint = head, fastPoint = head;
        while (true) {
            if (fastPoint == null || fastPoint.next == null) {
                return null;
            }
            fastPoint = fastPoint.next.next;
            slowPoint = slowPoint.next;
            if (slowPoint == fastPoint) {
                break;
            }
        }
        fastPoint = head;
        while (fastPoint != slowPoint) {
            fastPoint = fastPoint.next;
            slowPoint = slowPoint.next;
        }
        return fastPoint;
    }
}
